<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta 
    name="viewport"
    content="width=device-width, initial-scale=1.0, minimum-scale=1.0">
  <meta 
    http-equiv="X-UA-Compatible" 
    content="ie=edge">
  <meta 
    name="theme-color" 
    content="#fff" 
    id="theme-color">
  <meta 
    name="description" 
    content="霜序廿的个人网站">
  <link 
    rel="icon" 
    href="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
  <title>速度提高几百倍，记一次数据结构在实际工作中的运用</title>
  
    
      <meta 
        property="og:title" 
        content="速度提高几百倍，记一次数据结构在实际工作中的运用">
    
    
      <meta 
        property="og:url" 
        content="https://shuangxunian.github.io/2021/06/13/RememberTheUseOfDataStructuresInPracticalWork/index.html">
    
    
      <meta 
        property="og:img" 
        content="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
    
    
      <meta 
        property="og:img" 
        content="如题目">
    
    
      <meta 
        property="og:type" 
        content="article">
      <meta 
        property="og:article:published_time" 
        content="2021-06-13">
      <meta 
        property="og:article:modified_time" 
        content="2021-04-21">
      <meta 
        property="og:article:author" 
        content="霜序廿">
      
        
          <meta 
            property="og:article:tag" 
            content="js">
        
          <meta 
            property="og:article:tag" 
            content="轮子">
        
      
    
  
  <script>
    function loadScript(url, cb) {
      var script = document.createElement('script');
      script.src = url;
      if (cb) script.onload = cb;
      script.async = true;
      document.body.appendChild(script);
    }
    function loadCSS(href, data, attr) {
      var sheet = document.createElement('link');
      sheet.ref = 'stylesheet';
      sheet.href = href;
      sheet.dataset[data] = attr;
      document.head.appendChild(sheet);
    }
    function changeCSS(cssFile, data, attr) {
      var oldlink = document.querySelector(data);
      var newlink = document.createElement("link");
      newlink.setAttribute("rel", "stylesheet");
      newlink.setAttribute("href", cssFile);
      newlink.dataset.prism = attr;
      document.head.replaceChild(newlink, oldlink);
    }
  </script>
  
    
      
      
      
      
        
        
        
        <script>
          function prismThemeChange() {
            if(document.getElementById('theme-color').dataset.mode === 'dark') {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism-tomorrow.min.css', '[data-prism]', 'prism-tomorrow');
              } else {
                loadCSS('/js/lib/prism/prism-tomorrow.min.css', 'prism', 'prism-tomorrow');
              }
            } else {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism.min.css', '[data-prism]', 'prism');
              } else {
                loadCSS('/js/lib/prism/prism.min.css', 'prism', 'prism');
              }
            }
          }
          prismThemeChange()
        </script>
      
      
        
        <link rel="stylesheet" href="/js/lib/prism/prism-line-numbers.min.css">
      
    
  
  <script>
    // control reverse button
    var reverseDarkList = {
      dark: 'light',
      light: 'dark'
    };
    var themeColor = {
      dark: '#1c1c1e',
      light: '#fff'
    }
    // get the data of css prefers-color-scheme
    var getCssMediaQuery = function() {
      return window.matchMedia('(prefers-color-scheme: dark)').matches ? 'dark' : 'light';
    };
    // reverse current darkmode setting function
    var reverseDarkModeSetting = function() {
      var setting = localStorage.getItem('user-color-scheme');
      if(reverseDarkList[setting]) {
        setting = reverseDarkList[setting];
      } else if(setting === null) {
        setting = reverseDarkList[getCssMediaQuery()];
      } else {
        return;
      }
      localStorage.setItem('user-color-scheme', setting);
      return setting;
    };
    // apply current darkmode setting
  </script>
  
    <script>
      var setDarkmode = function(mode) {
      var setting = mode || localStorage.getItem('user-color-scheme');
      if(setting === getCssMediaQuery()) {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else if(reverseDarkList[setting]) {
        document.documentElement.setAttribute('data-user-color-scheme', setting);
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[getCssMediaQuery()];
        document.getElementById('theme-color').dataset.mode = getCssMediaQuery();
        prismThemeChange();
      }
    };
    setDarkmode();
    </script>
  
  
  <link rel="preload" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css" as="style" >
  <link rel="preload" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.js" as="script">
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lozad.min.js" as="script">
  
  
  
  
  
  
  
  <link rel="stylesheet" href="/css/main.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css">
  
    <link rel="stylesheet" href="/js/lib/lightbox/baguetteBox.min.css">
  
<meta name="generator" content="Hexo 5.4.0"></head>

  <body>
    <div class="wrapper">
       
      <nav class="navbar">
  <div class="navbar-logo">
    <span class="navbar-logo-main">
      
        <img 
          class="navbar-logo-img" 
          src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
          alt="blog logo">
      
      <span class="navbar-logo-dsc">霜序廿的个人网站</span>
    </span>
  </div>
  <div class="navbar-menu">
    
      <a 
        href="/" 
        class="navbar-menu-item">
        
          首页
        
      </a>
    
      <a 
        href="/archives" 
        class="navbar-menu-item">
        
          归档
        
      </a>
    
      <a 
        href="/tags" 
        class="navbar-menu-item">
        
          标签
        
      </a>
    
      <a 
        href="/categories" 
        class="navbar-menu-item">
        
          分类
        
      </a>
    
      <a 
        href="/about" 
        class="navbar-menu-item">
        
          关于
        
      </a>
    
      <a 
        href="/links" 
        class="navbar-menu-item">
        
          友链
        
      </a>
    
    <a 
      class="navbar-menu-item darknavbar" 
      id="dark">
      <i class="iconfont icon-weather"></i>
    </a>
    <a 
      class="navbar-menu-item searchnavbar" 
      id="search">
      <i 
        class="iconfont icon-search" 
        style="font-size: 1.2rem; font-weight: 400;">
      </i>
    </a>
  </div>
</nav> 
      
      <div 
        id="local-search" 
        style="display: none">
        <input
          class="navbar-menu-item"
          id="search-input"
          placeholder="请输入搜索内容..." />
        <div id="search-content"></div>
      </div>
      
      <div class="section-wrap">
        <div class="container">
          <div class="columns">
            <main class="main-column">
<article class="card card-content">
  <header>
    <h1 class="post-title">
      速度提高几百倍，记一次数据结构在实际工作中的运用
    </h1>
  </header>
  <div class="post-meta post-show-meta">
    <time datetime="2021-06-13T13:48:56.227Z">
      <i 
        class="iconfont icon-calendar" 
        style="margin-right: 2px;">
      </i>
      <span>2021-06-13</span>
    </time>
    
      <span class="dot"></span>
      
        <a 
          href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/" 
          class="post-meta-link">
          技术文章
        </a>
      
    
    
      <span class="dot"></span>
      <span>5.2k 字</span>
    
  </div>
  
    <div 
      class="post-meta post-show-meta" 
      style="margin-top: -10px;">
      <div style="display: flex; align-items: center;">
        <i 
          class="iconfont icon-biaoqian" 
          style="margin-right: 2px; font-size: 1.15rem;">
        </i>
        
          
          <a 
            href="/tags/js/" 
            class="post-meta-link">
            js
          </a>
        
          
            <span class="dot"></span>
          
          <a 
            href="/tags/%E8%BD%AE%E5%AD%90/" 
            class="post-meta-link">
            轮子
          </a>
        
      </div>
    </div>
  
  </header>
  <div 
    id="section" 
    class="post-content">
    <h2 id="需求"><a href="#需求" class="headerlink" title="需求"></a>需求</h2><p>有这样一个需求：需要支持三层的产品选项</p>
<p>一般电商系统都是两层的产品选项，如果打开手机挨个软件看一下，在我看过的商品中，没有发现一个商品有三层选项的，最多也就两层。</p>
<h2 id="为什么没人做三层选项"><a href="#为什么没人做三层选项" class="headerlink" title="为什么没人做三层选项"></a>为什么没人做三层选项</h2><p>一两家不做这个，可能是各家的需求不一样，但是大家都不做，感觉事情不对头。经过仔细分析后，我觉得不做三层选项可能有以下两个原因：</p>
<ol>
<li>这可能是个伪需求<br> 上面这个鞋子有11种颜色，11种尺码，意味着这些选项后面对应的是11 * 11，总共121个商品。如果再来个第三层选项，假设第三层也有11个选项，那对应的商品总共就是11 * 11 * 11，也就是1331个商品，好多店铺总共可能都没有1331个商品。也就是说，第三层选项可能是个伪需求，用户并没有那么多选项放在第三层，还是以上面的鞋子为例，除了颜色，尺码外，非要再添一个层级，那只能是性别了，也就是男鞋和女鞋。对于男鞋和女鞋来说，版型，尺码这些很不一样，一般都不会放到一个商品下面，更常用的做法是分成两个商品，各自有自己的颜色和尺码。</li>
<li>有性能问题<br> 仅仅是加上第三层选项这个功能并没有什么难的，也就是多展示几个可以点击的按钮而已，点击逻辑跟两层选项并没有太大区别。但是细想下去，我发现了他有潜在的性能问题。以上面这双鞋子为例，我从后端API拿到的数据是这样的： <pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">const</span> merchandise <span class="token operator">=</span> <span class="token punctuation">&#123;</span>
<span class="token comment">// variations存放的是所有选项</span>
variations<span class="token operator">:</span> <span class="token punctuation">[</span>
    <span class="token punctuation">&#123;</span>
    name<span class="token operator">:</span> <span class="token string">'颜色'</span><span class="token punctuation">,</span>
    values<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'限量版574海军蓝'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'限量版574白粉'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token comment">// 下面还有9个</span>
    <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#123;</span>
    name<span class="token operator">:</span> <span class="token string">'尺码'</span><span class="token punctuation">,</span>
    values<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'38'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'39'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token comment">// 下面还有9个</span>
    <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
<span class="token punctuation">]</span><span class="token punctuation">,</span>
<span class="token comment">// products数组存放的是所有商品</span>
products<span class="token operator">:</span> <span class="token punctuation">[</span>
    <span class="token punctuation">&#123;</span>
    id<span class="token operator">:</span> <span class="token number">1</span><span class="token punctuation">,</span>
    price<span class="token operator">:</span> <span class="token number">208</span><span class="token punctuation">,</span>
    <span class="token comment">// 与上面variations的对应关系在每个商品的variationMappings里面</span>
    variationMappings<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'颜色'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'限量版574白粉'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'尺码'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'38'</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token comment">// 下面还有一百多个产品</span>
<span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
 上面这个结构本身还是挺清晰的，merchandise.variations是一个数组，有几层选项，这个数组就有几个对象，每个对象的name就是当前层级的名字，values就是当前层级包含的选项，所以merchandise.variations可以直接拿来显示在UI上，将他们按照层级渲染成按钮就行。</li>
</ol>
<p>如果用户选择了第一层的限量版574白粉，第二层的40，41等不存在的商品就自动灰掉了。用上面的数据结构可以做到这个功能，当用户选择限量版574白粉的时候，我们就去遍历merchandise.products这个数组，这个数组的一个项就是一个商品，这个商品上的variationMappings会有当前商品的颜色和尺码信息。对于我当前的项目来说，如果这个商品可以卖，他就会在merchandise.products这个数组里面，如果不可以卖，这个数组里面压根就不会有这个商品。比如上图的限量版574白粉，40码的组合就不会出现在merchandise.products里面，查找的时候找不到这个组合，那就会将它变为灰色，不可以点。</p>
<p>所以对于限量版574白粉，40这个鞋子来说，为了知道它需不需要灰掉，我需要整个遍历merchandise.products这个数组。按照前面说的11个颜色，11个尺码来说，最多会有121个商品，也就是最多查找121次。同样的要知道限量版574白粉，41这个商品可以不可以卖，又要整个遍历商品数组，11个尺码就需要将商品数组整个遍历11次。对于两层选项来说，11 * 11已经算比较多的了，每个尺码百来次运算可能还不会有严重的性能问题。但是如果再加一层选项，新加这层假如也有11个可选项，这复杂度瞬间就增加了一个指数，从O(n2)变成O(n3)！现在我们的商品总数是11 * 11 * 11，也就是1331个商品，假如第三层是性别，现在为了知道限量版574白粉，40，男性这个商品可不可以卖，我需要遍历1331个商品，如果遍历121个商品需要20ms，还比较流畅，那遍历1331个商品就需要220ms，这明显可以感觉到卡顿了，在某些硬件较差的设备上，这种卡顿会更严重，变得不可接受了。而且我们APP使用的技术是React Native，本身性能就比原生差，这样一来，用户可能就怒而卸载了！</p>
<p>我拿着上述对需求的疑问，和对性能的担心找到了产品经理，发生了如下对话：</p>
<blockquote>
<p>我：大佬，我发现市面上好像没有APP支持三层选项的，这个需求是不是有问题哦，而且三层选项相较于两层选项来说，复杂度是指数增长，可能会有性能问题，用户用起来会卡的。</p>
<p>产品经理：兄弟，你看的都是国内的APP，但是我们这个是给外国人用的，人家外国人就是习惯这么用，咱要想卖的出去就得满足他们的需求。太卡了肯定不行，性能问题，想办法解决嘛，这就是在UI上再加几个按钮，设计图都跟以前是一样的，给你两天时间够了吧~</p>
<p>我：啊！？额。。。哦。。。</p>
</blockquote>
<p>咱也不认识几个外国人，咱也不敢再问，都说了是用户需求，咱必须满足了产品才卖的出去，产品卖出去了咱才有饭吃，想办法解决吧！</p>
<h2 id="解决方案"><a href="#解决方案" class="headerlink" title="解决方案"></a>解决方案</h2><p>看来这个需求是必须要做了，这个功能并不复杂，因为三层选项可以沿用两层选项的方案，继续去遍历商品数组，但是这个复杂度增长是指数级的，即从O(n2)变成O(n3)，用户用起来会卡。现在，我需要思考一下，有没有其他方案可以提高性能。经过仔细思考，我发现，这种指数级的复杂度增长是来自于我们整个数组的遍历，如果我能够找到一个方法不去遍历这个数组，立即就能找到限量版574白粉，40，男性对应的商品存不存在就好了。</p>
<p>这个具体的问题转换一下，其实就是：在一个数组中，通过特定的过滤条件，查找符合条件的一个项。嗯，查找，听起来蛮耳熟的，现在我之所以需要去遍历这个数组，是因为这些查找条件跟商品间没有一个直接的对应关系，如果我能建立一个直接的对应关系，不就可以一下就找到了吗？我想到了：查找树。假如我重组这些层级关系，将它们组织为一颗树，每个商品都对应树上的一个叶子节点，我可以将三层选项的查找复杂度从O(n3)降到O(1)。</p>
<h3 id="两层查找树"><a href="#两层查找树" class="headerlink" title="两层查找树"></a>两层查找树</h3><p>为了说明白这个算法，我先简化这个问题，假设我们现在有两层选项，颜色和尺码，每层选项有两个可选项：</p>
<ol>
<li>颜色：白色，红色</li>
<li>尺码：39，40</li>
</ol>
<p>我们现在对应有4个商品：</p>
<ol>
<li>一号商品：productId为1，白色，39码</li>
<li>二号商品：productId为2，白色，40码</li>
<li>三号商品：productId为3，红色，39码</li>
<li>四号商品：productId为4，红色，40码<br>如果按照最简单的做法，为了查找红色的39码鞋子存不存在，我们需要遍历所有的这四个商品，这时候的时间复杂度为O(n2)。但是如果我们构建像下面这样一颗树，可以将时间复杂度降到O(1)：</li>
</ol>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/bc03a808-ebcb-48ff-b2d7-a4f55d128459-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/bc03a808-ebcb-48ff-b2d7-a4f55d128459-3807603.jpg"></p>
<p>上面这颗树，我们忽略root节点，在本例中他并没有什么用，仅仅是一个树的入口，这棵树的第一层淡黄色节点是我们第一层选项颜色，第二层淡蓝色节点是我们的第二层选项尺码，只是每个颜色节点都会对应所有的尺码，这样我们最后第二层的叶子节点其实就对应了具体的商品。现在我们要查找红色的39码鞋子，只需要看图中红色箭头指向的节点上有没有商品就行了。</p>
<p>那这种数据结构在JS中该怎么表示呢？其实很简单，一个对象就行了，像这样：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">const</span> tree <span class="token operator">=</span> <span class="token punctuation">&#123;</span>
  <span class="token string">"颜色：白色"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span>
    <span class="token string">"尺码：39"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">1</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token string">"尺码：40"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">2</span> <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
  <span class="token string">"颜色：红色"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span>
    <span class="token string">"尺码：39"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">3</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token string">"尺码：40"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">4</span> <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>有了上面这个数据结构，我们要查找红色的39码直接取值<code>tree[&quot;颜色：红色&quot;][&quot;尺码：39&quot;]</code>就行了，这个复杂度瞬间就变为O(1)了。</p>
<h3 id="三层查找树"><a href="#三层查找树" class="headerlink" title="三层查找树"></a>三层查找树</h3><p>理解了上面的两层查找树，要将它扩展到三层就简单了，直接再加一层就行了。假如我们现在第三层选项是性别，有两个可选项男和女，那我们的查找树就是这样子的：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/b84d50af-4611-4c6c-9ce1-8f8ff0fa2089-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/b84d50af-4611-4c6c-9ce1-8f8ff0fa2089-3807603.jpg"></p>
<p>对应的JS对象：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">const</span> tree <span class="token operator">=</span> <span class="token punctuation">&#123;</span>
  <span class="token string">"颜色：白色"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span>
    <span class="token string">"尺码：39"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> 
    	<span class="token string">"性别：男"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">1</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token string">"性别：女"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">2</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token string">"尺码：40"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> 
    	<span class="token string">"性别：男"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">3</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token string">"性别：女"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">4</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
  <span class="token string">"颜色：红色"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span>
    <span class="token string">"尺码：39"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> 
    	<span class="token string">"性别：男"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">5</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token string">"性别：女"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">6</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token string">"尺码：40"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> 
    	<span class="token string">"性别：男"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">7</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token string">"性别：女"</span><span class="token operator">:</span> <span class="token punctuation">&#123;</span> productId<span class="token operator">:</span> <span class="token number">8</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>同样的，假如我们要查找一个白色的，39码，男的鞋子，直接<code>tree[&quot;颜色：白色&quot;][&quot;尺码：39&quot;][&quot;性别：男&quot;]</code>就行了，这个时间复杂度也是O(1)。</p>
<h3 id="写代码"><a href="#写代码" class="headerlink" title="写代码"></a>写代码</h3><p>上面算法都弄明白了，剩下的就是写代码了，我们主要需要写的代码就是用API返回的数据构建一个上面的tree这种结构就行了，一次遍历就可以做到。比如上面这个三层查找树对应的API返回的结构是这样的：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">const</span> merchandise <span class="token operator">=</span> <span class="token punctuation">&#123;</span>
  variations<span class="token operator">:</span> <span class="token punctuation">[</span>
    <span class="token punctuation">&#123;</span>
      name<span class="token operator">:</span> <span class="token string">'颜色'</span><span class="token punctuation">,</span>
      values<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'白色'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'红色'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#123;</span>
      name<span class="token operator">:</span> <span class="token string">'尺码'</span><span class="token punctuation">,</span>
      values<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'39'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'40'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
    <span class="token punctuation">&#123;</span>
      name<span class="token operator">:</span> <span class="token string">'性别'</span><span class="token punctuation">,</span>
      values<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'男'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'女'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
      <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
  <span class="token punctuation">]</span><span class="token punctuation">,</span>
  products<span class="token operator">:</span> <span class="token punctuation">[</span>
    <span class="token punctuation">&#123;</span>
      id<span class="token operator">:</span> <span class="token number">1</span><span class="token punctuation">,</span>
      variationMappings<span class="token operator">:</span> <span class="token punctuation">[</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'颜色'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'白色'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'尺码'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'39'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
        <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'性别'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'男'</span> <span class="token punctuation">&#125;</span>
      <span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span>
    <span class="token comment">// 下面还有7个商品，我就不重复了</span>
  <span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>为了将API返回的数据转换为我们的树形结构数据我们写一个方法：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">buildTree</span><span class="token punctuation">(</span><span class="token parameter">apiData</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">const</span> tree <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
  <span class="token keyword">const</span> <span class="token punctuation">&#123;</span> variations<span class="token punctuation">,</span> products <span class="token punctuation">&#125;</span> <span class="token operator">=</span> apiData<span class="token punctuation">;</span>

  <span class="token comment">// 先用variations将树形结构构建出来，叶子节点默认值为null</span>
  <span class="token function">addNode</span><span class="token punctuation">(</span>tree<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">function</span> <span class="token function">addNode</span><span class="token punctuation">(</span><span class="token parameter">root<span class="token punctuation">,</span> deep</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> variationName <span class="token operator">=</span> variations<span class="token punctuation">[</span>deep<span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token punctuation">;</span>
    <span class="token keyword">const</span> variationValues <span class="token operator">=</span> variations<span class="token punctuation">[</span>deep<span class="token punctuation">]</span><span class="token punctuation">.</span>values<span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> variationValues<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
      <span class="token keyword">const</span> nodeName <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationName<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationValues<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>deep <span class="token operator">===</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">null</span>
      <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
        root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
        <span class="token function">addNode</span><span class="token punctuation">(</span>root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span><span class="token punctuation">,</span> deep <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span>

  <span class="token comment">// 然后遍历一次products给树的叶子节点填上值</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> products<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> product <span class="token operator">=</span> products<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> <span class="token punctuation">&#123;</span> variationMappings <span class="token punctuation">&#125;</span> <span class="token operator">=</span> product<span class="token punctuation">;</span>
    <span class="token keyword">const</span> level1Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> level2Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> level3Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    tree<span class="token punctuation">[</span>level1Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level2Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level3Name<span class="token punctuation">]</span> <span class="token operator">=</span> product<span class="token punctuation">;</span>
  <span class="token punctuation">&#125;</span>

  <span class="token comment">// 最后返回构建好的树</span>
  <span class="token keyword">return</span> tree<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/a020109c-a355-451f-b86e-49a49fa61247-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/a020109c-a355-451f-b86e-49a49fa61247-3807603.jpg"></p>
<h3 id="这就好了吗？"><a href="#这就好了吗？" class="headerlink" title="这就好了吗？"></a>这就好了吗？</h3><p>现在我们有了一颗查找树，当用户选择红色，40码后，为了知道对应的男可不可以点，我们不需要去遍历所有的商品了，而是可以直接从这个结构上取值。但是这就大功告成了吗？并没有！再仔细看下我们构建出来的数据结构，层级关系是固定的，第一层是颜色，第二层是尺码，第三层是性别，而对应的商品是放在第三层性别上的。也就是说使用这个结构，用户必须严格按照，先选颜色，再选尺码，然后我们看看性别这里哪个该灰掉。如果他不按照这个顺序，比如他先选了性别男，然后选尺码40，这时候我们应该计算最后一个层级颜色哪些该灰掉。但是使用上面这个结构我们是算不出来的，因为我们并没有<code>tree[&quot;性别：男&quot;][&quot;尺码：40&quot;]</code>这个对象。</p>
<p>这怎么办呢？我们没有性别-尺码-颜色这种顺序的树，那我们就建一颗呗！这当然是个方法，但是用户还可能有其他的操作顺序呀，如果我们要覆盖用户所有可能的操作顺序，总共需要多少树呢？这其实是性别，尺码，颜色这三个变量的一个全排列，也就是A33，总共6颗树。像我这样的懒人，让我建6棵树，我实在懒得干。如果不建这么多树，需求又覆盖不了，怎么办呢，有没有偷懒的办法呢？如果我能在需求上动点手脚，是不是可以规避这个问题？带着这个思路，我想到了两点：</p>
<ol>
<li>给一个默认值。<br>用户打开商品详情页的时候，默认选中第一个可售商品。这样就相当于我们一开始就帮用户按照颜色-尺码-性别这个顺序选中了一个值，给了他一个默认的操作顺序。</li>
<li>不提供取消功能，只能切换选项<br>如果提供取消功能，他将我们提供的颜色-尺码-性别默认选项取消掉，又可以选成性别-尺码-颜色了。不提供取消功能，只能通过选择其他选项来切换，只能从红色换成白色，而不能取消红色，其他的一样。这样我们就能永远保证颜色-尺码-性别这个顺序，用户操作只是只是每个层级选中的值不一样，层级顺序并不会变化，我们的查找树就一直有效了。而且我发现某些购物网站也不能取消选项，不知道他们是不是也遇到了类似的问题。</li>
</ol>
<p>对需求做这两点修改并不会对用户体验造成多大影响，跟产品经理商量后，她也同意了。这样我就从需求上干掉了另外5棵树，偷懒成功！</p>
<h3 id="还有一件事"><a href="#还有一件事" class="headerlink" title="还有一件事"></a>还有一件事</h3><p>前面的方案我们解决了查找的性能问题，但是引入了一个新问题，那就是需要创建这颗查找树。创建这颗查找树还是需要对商品列表进行一次遍历，这是不可避免的，为了更顺滑的用户体验，我们应该尽量将这个创建过程隐藏在用户感知不到的地方。我这里是将它整合到了商品详情页的加载状态中，用户点击进入商品详情页，我们要去API取数据，不可避免的会有一个加载状态，会转个圈什么的。我将这个遍历过程也做到了这个转圈中，当API数据返回，并且查找树创建完成后，转圈才会结束。这在理论上会延长转圈的时间，但是本地的遍历再慢也会比网络请求快点，所以用户感知并不明显。当转圈结束后，所有数据都准备就绪了，用户操作都是O(1)的复杂度，做到了真正的丝般顺滑~</p>
<h3 id="为什么不让后端创建这棵树？"><a href="#为什么不让后端创建这棵树？" class="headerlink" title="为什么不让后端创建这棵树？"></a>为什么不让后端创建这棵树？</h3><p>上面的方案都是在前端创建这颗树，那有没有可能后端一开始返回的数据就是这样的，我直接拿来用就行，这样我又可以偷懒了~我还真去找过后端，可他给我说：“我也想偷懒！”开个玩笑，真是情况是，这个商品API是另一个团队维护的微服务，他们提供的数据不仅仅给我这一个终端APP使用，也给公司其他产品使用，所以要改返回结构涉及面太大，根本改不动。</p>
<h3 id="封装代码"><a href="#封装代码" class="headerlink" title="封装代码"></a>封装代码</h3><p>其实我们这个方案实现本身是比较独立的，其他人要是用的话，他也不关心你里面是棵树还是颗草，只要传入选择条件，能够返回正确的商品就行，所以我们可以将它封装成一个类。</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">class</span> <span class="token class-name">VariationSearchMap</span> <span class="token punctuation">&#123;</span>
  <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">apiData</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>tree <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">buildTree</span><span class="token punctuation">(</span>apiData<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">&#125;</span>

  <span class="token comment">// 这就是前面那个构造树的方法</span>
  <span class="token function">buildTree</span><span class="token punctuation">(</span><span class="token parameter">apiData</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> tree <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> <span class="token punctuation">&#123;</span> variations<span class="token punctuation">,</span> products <span class="token punctuation">&#125;</span> <span class="token operator">=</span> apiData<span class="token punctuation">;</span>

    <span class="token comment">// 先用variations将树形结构构建出来，叶子节点默认值为null</span>
    <span class="token function">addNode</span><span class="token punctuation">(</span>tree<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">function</span> <span class="token function">addNode</span><span class="token punctuation">(</span><span class="token parameter">root<span class="token punctuation">,</span> deep</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
      <span class="token keyword">const</span> variationName <span class="token operator">=</span> variations<span class="token punctuation">[</span>deep<span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token punctuation">;</span>
      <span class="token keyword">const</span> variationValues <span class="token operator">=</span> variations<span class="token punctuation">[</span>deep<span class="token punctuation">]</span><span class="token punctuation">.</span>values<span class="token punctuation">;</span>

      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> variationValues<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">const</span> nodeName <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationName<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationValues<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>deep <span class="token operator">===</span> variations<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
          root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
          root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
          <span class="token function">addNode</span><span class="token punctuation">(</span>root<span class="token punctuation">[</span>nodeName<span class="token punctuation">]</span><span class="token punctuation">,</span> deep <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
      <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">// 然后遍历一次products给树的叶子节点填上值</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> products<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
      <span class="token keyword">const</span> product <span class="token operator">=</span> products<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
      <span class="token keyword">const</span> <span class="token punctuation">&#123;</span> variationMappings <span class="token punctuation">&#125;</span> <span class="token operator">=</span> product<span class="token punctuation">;</span>
      <span class="token keyword">const</span> level1Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">const</span> level2Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      <span class="token keyword">const</span> level3Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
      tree<span class="token punctuation">[</span>level1Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level2Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level3Name<span class="token punctuation">]</span> <span class="token operator">=</span> product<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">// 最后返回构建好的树</span>
    <span class="token keyword">return</span> tree<span class="token punctuation">;</span>
  <span class="token punctuation">&#125;</span>

  <span class="token comment">// 添加一个方法来搜索商品，参数结构和API数据的variationMappings一样</span>
  <span class="token function">findProductByVariationMappings</span><span class="token punctuation">(</span><span class="token parameter">variationMappings</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> level1Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> level2Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> level3Name <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>name<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token string">：</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">$&#123;</span>variationMappings<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span>value<span class="token interpolation-punctuation punctuation">&#125;</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

    <span class="token keyword">const</span> product <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tree<span class="token punctuation">[</span>level1Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level2Name<span class="token punctuation">]</span><span class="token punctuation">[</span>level3Name<span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> product<span class="token punctuation">;</span>
  <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>然后使用的时候直接new一下就行：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">const</span> variationSearchMap <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">VariationSearchMap</span><span class="token punctuation">(</span>apiData<span class="token punctuation">)</span><span class="token punctuation">;</span>    <span class="token comment">// new一个实例出来</span>

<span class="token comment">// 然后就可以用这个实例进行搜索了</span>
<span class="token keyword">const</span> searchCriteria <span class="token operator">=</span> <span class="token punctuation">[</span>
  <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'颜色'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'红色'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
  <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'尺码'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'40'</span> <span class="token punctuation">&#125;</span><span class="token punctuation">,</span>
  <span class="token punctuation">&#123;</span> name<span class="token operator">:</span> <span class="token string">'性别'</span><span class="token punctuation">,</span> value<span class="token operator">:</span> <span class="token string">'女'</span> <span class="token punctuation">&#125;</span>
<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> matchedProduct <span class="token operator">=</span> variationSearchMap<span class="token punctuation">.</span><span class="token function">findProductByVariationMappings</span><span class="token punctuation">(</span>searchCriteria<span class="token punctuation">)</span><span class="token punctuation">;</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">'matchedProduct'</span><span class="token punctuation">,</span> matchedProduct<span class="token punctuation">)</span><span class="token punctuation">;</span>    <span class="token comment">// &#123; productId: 8 &#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>本文讲述了一个我工作中实际遇到的需求，分享了我的实现和优化思路，供大家参考。我的实现方案不一定完美，如果大家有更好的方案，欢迎在评论区讨论~</p>
<p>下面再来回顾下本文的要点：</p>
<ol>
<li>本文要实现的需求是一个商品的三层选项。</li>
<li>当用户选择了两层后，第三层选项应该自动计算出哪些能卖，哪些不能卖。</li>
<li>鉴于后端API返回选项和商品间没有直接的对应关系，为了找出能卖还是不能卖，我们需要遍历所有商品。</li>
<li>当总商品数量不多的时候，所有商品遍历可能不会产生明显的性能问题。</li>
<li>但是当选项增加到三层，商品数量的增加是指数级的，性能问题就会显现出来。</li>
<li>对于O(n3)这种写代码时就能预见的性能问题，我们不用等着报BUG了才处理，而是开发时直接就解决了。</li>
<li>本例要解决的是一个查找问题，所以我想到了建一颗树，直接将O(n3)的复杂度降到了O(1)。</li>
<li>但是一颗树并不能覆盖所有的用户操作，要覆盖所有的用户操作需要6棵树。</li>
<li>出于偷懒的目的，我跟产品经理商量，调整了需求和交互砍掉了5颗树。真实原因是树太多了，会占用更多的内存空间，也不好维护。有时候适当的调整需求和交互也可以达到优化性能的效果，性能优化可以将交互和技术结合起来思考。</li>
<li>这个树的搜索模块可以单独封装成一个类，外部使用者，不需要知道细节，直接调用接口查找就行。</li>
<li>前端会点数据结构还是有用的，本文这种场景下还很有必要。</li>
</ol>
<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/dennisj/p/14030280.html">速度提高几百倍，记一次数据结构在实际工作中的运用</a></p>

  </div>
  <div>
    
  </div>
</article>
<div class="nav">
  
    <div class="nav-item-prev">
      <a 
        href="/2021/06/13/removesTheHorizontalScrollBarFromTheDIVDisplay/" 
        class="nav-link">
        <i class="iconfont icon-left nav-prev-icon"></i>
        <div>
          <div class="nav-label">上一篇</div>
          
            <div class="nav-title">去除div显示的横向滚动条 </div>
          
        </div>
      </a>
    </div>
  
  
    <div class="nav-item-next">
      <a 
        href="/2021/06/13/reflowAndRepaint/" 
        class="nav-link">
        <div>
          <div class="nav-label">下一篇</div>
          
            <div class="nav-title">重排(reflow)和重绘(repaint) </div>
          
        </div>
        <i class="iconfont icon-right nav-next-icon"></i>
      </a>
    </div>
  
</div>

<div 
  class="card card-content toc-card" 
  id="mobiletoc">
  <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%9C%80%E6%B1%82"><span class="toc-text">需求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E6%B2%A1%E4%BA%BA%E5%81%9A%E4%B8%89%E5%B1%82%E9%80%89%E9%A1%B9"><span class="toc-text">为什么没人做三层选项</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%A7%A3%E5%86%B3%E6%96%B9%E6%A1%88"><span class="toc-text">解决方案</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%A4%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">两层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%89%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">三层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%86%99%E4%BB%A3%E7%A0%81"><span class="toc-text">写代码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%99%E5%B0%B1%E5%A5%BD%E4%BA%86%E5%90%97%EF%BC%9F"><span class="toc-text">这就好了吗？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%98%E6%9C%89%E4%B8%80%E4%BB%B6%E4%BA%8B"><span class="toc-text">还有一件事</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E8%AE%A9%E5%90%8E%E7%AB%AF%E5%88%9B%E5%BB%BA%E8%BF%99%E6%A3%B5%E6%A0%91%EF%BC%9F"><span class="toc-text">为什么不让后端创建这棵树？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%81%E8%A3%85%E4%BB%A3%E7%A0%81"><span class="toc-text">封装代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
</div></main>
            <aside class="left-column">
              
              <div class="card card-author">
                
  <img 
    src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
    class="author-img" 
    alt="author avatar">

<p class="author-name">霜序廿</p>
<p class="author-description">无限进步</p>
<div class="author-message">
  <a 
    class="author-posts-count" 
    href="/archives">
    <span>253</span>
    <span>文章</span>
  </a>
  <a 
    class="author-categories-count" 
    href="/categories">
    <span>6</span>
    <span>分类</span>
  </a>
  <a 
    class="author-tags-count" 
    href="/tags">
    <span>51</span>
    <span>标签</span>
  </a>
</div>

  <div class="author-card-society">
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://github.com/shuangxunian">
          <i class="iconfont icon-github society-icon"></i>
        </a>
      </div>
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://space.bilibili.com/391117803">
          <i class="iconfont icon-bilibili society-icon"></i>
        </a>
      </div>
    
  </div>

              </div>
               <div class="sticky-tablet">
  
  
    <article class="display-when-two-columns spacer">
      <div class="card card-content toc-card">
        <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%9C%80%E6%B1%82"><span class="toc-text">需求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E6%B2%A1%E4%BA%BA%E5%81%9A%E4%B8%89%E5%B1%82%E9%80%89%E9%A1%B9"><span class="toc-text">为什么没人做三层选项</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%A7%A3%E5%86%B3%E6%96%B9%E6%A1%88"><span class="toc-text">解决方案</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%A4%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">两层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%89%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">三层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%86%99%E4%BB%A3%E7%A0%81"><span class="toc-text">写代码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%99%E5%B0%B1%E5%A5%BD%E4%BA%86%E5%90%97%EF%BC%9F"><span class="toc-text">这就好了吗？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%98%E6%9C%89%E4%B8%80%E4%BB%B6%E4%BA%8B"><span class="toc-text">还有一件事</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E8%AE%A9%E5%90%8E%E7%AB%AF%E5%88%9B%E5%BB%BA%E8%BF%99%E6%A3%B5%E6%A0%91%EF%BC%9F"><span class="toc-text">为什么不让后端创建这棵树？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%81%E8%A3%85%E4%BB%A3%E7%A0%81"><span class="toc-text">封装代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
      </div>
    </article>
  
  
  <article class="card card-content categories-widget">
    <div class="categories-card">
  <div class="categories-header">
    <i 
      class="iconfont icon-fenlei" 
      style="padding-right: 2px;">
    </i>分类
  </div>
  <div class="categories-list">
    
      <a href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/">
        <div class="categories-list-item">
          技术文章
          <span class="categories-list-item-badge">218</span>
        </div>
      </a>
    
      <a href="/categories/%E5%85%B6%E4%BB%96/">
        <div class="categories-list-item">
          其他
          <span class="categories-list-item-badge">16</span>
        </div>
      </a>
    
      <a href="/categories/%E6%97%85%E6%B8%B8/">
        <div class="categories-list-item">
          旅游
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
      <a href="/categories/%E7%AE%97%E6%B3%95/">
        <div class="categories-list-item">
          算法
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E8%80%83%E8%AF%95/">
        <div class="categories-list-item">
          考试
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E9%98%85%E8%AF%BB/">
        <div class="categories-list-item">
          阅读
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
  </div>
</div>
  </article>
  
  <article class="card card-content tags-widget">
    <div class="tags-card">
  <div class="tags-header">
    <i 
      class="iconfont icon-biaoqian" 
      style="padding-right: 2px;">
    </i>热门标签
  </div>
  <div class="tags-list">
    
      <a 
        href="/tags/js/" 
        title="js">
        <div class="tags-list-item">js</div>
      </a>
    
      <a 
        href="/tags/vue/" 
        title="vue">
        <div class="tags-list-item">vue</div>
      </a>
    
      <a 
        href="/tags/%E9%9D%A2%E8%AF%95/" 
        title="面试">
        <div class="tags-list-item">面试</div>
      </a>
    
      <a 
        href="/tags/css/" 
        title="css">
        <div class="tags-list-item">css</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C/" 
        title="网络">
        <div class="tags-list-item">网络</div>
      </a>
    
      <a 
        href="/tags/%E5%85%B6%E4%BB%96/" 
        title="其他">
        <div class="tags-list-item">其他</div>
      </a>
    
      <a 
        href="/tags/%E7%AE%97%E6%B3%95/" 
        title="算法">
        <div class="tags-list-item">算法</div>
      </a>
    
      <a 
        href="/tags/%E6%B5%8F%E8%A7%88%E5%99%A8/" 
        title="浏览器">
        <div class="tags-list-item">浏览器</div>
      </a>
    
      <a 
        href="/tags/html/" 
        title="html">
        <div class="tags-list-item">html</div>
      </a>
    
      <a 
        href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" 
        title="操作系统">
        <div class="tags-list-item">操作系统</div>
      </a>
    
      <a 
        href="/tags/%E8%80%83%E8%AF%95/" 
        title="考试">
        <div class="tags-list-item">考试</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AF%E5%AE%9E%E5%8A%9B/" 
        title="软实力">
        <div class="tags-list-item">软实力</div>
      </a>
    
      <a 
        href="/tags/DOM/" 
        title="DOM">
        <div class="tags-list-item">DOM</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AE%E5%AD%90/" 
        title="轮子">
        <div class="tags-list-item">轮子</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C%E5%8E%9F%E7%90%86/" 
        title="网络原理">
        <div class="tags-list-item">网络原理</div>
      </a>
    
      <a 
        href="/tags/debug/" 
        title="debug">
        <div class="tags-list-item">debug</div>
      </a>
    
  </div>
</div>
  </article>
  
  
</div>
            </aside>
            <aside class="right-column">
              <div class="sticky-widescreen">
  
  
    <article class="card card-content toc-card">
      <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%9C%80%E6%B1%82"><span class="toc-text">需求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E6%B2%A1%E4%BA%BA%E5%81%9A%E4%B8%89%E5%B1%82%E9%80%89%E9%A1%B9"><span class="toc-text">为什么没人做三层选项</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%A7%A3%E5%86%B3%E6%96%B9%E6%A1%88"><span class="toc-text">解决方案</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%A4%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">两层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%89%E5%B1%82%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-text">三层查找树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%86%99%E4%BB%A3%E7%A0%81"><span class="toc-text">写代码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%99%E5%B0%B1%E5%A5%BD%E4%BA%86%E5%90%97%EF%BC%9F"><span class="toc-text">这就好了吗？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%98%E6%9C%89%E4%B8%80%E4%BB%B6%E4%BA%8B"><span class="toc-text">还有一件事</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E8%AE%A9%E5%90%8E%E7%AB%AF%E5%88%9B%E5%BB%BA%E8%BF%99%E6%A3%B5%E6%A0%91%EF%BC%9F"><span class="toc-text">为什么不让后端创建这棵树？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B0%81%E8%A3%85%E4%BB%A3%E7%A0%81"><span class="toc-text">封装代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
    </article>
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    <i 
      class="iconfont icon-wenzhang_huaban" 
      style="padding-right: 2px;">
    </i>最近文章
  </div>
  <div class="recent-posts-list">
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-05-01</div>
        <a href="/2022/05/01/typescriptHome/"><div class="recent-posts-item-content">typescript</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptTheVariousWaysAndAdvantagesAndDisadvantagesOfDeepInheritance/"><div class="recent-posts-item-content">JavaScript深入之继承的多种方式和优缺点</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptGoFromPrototypeToPrototypeChain/"><div class="recent-posts-item-content">JavaScript深入之从原型到原型链</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptMemoryLeakTutorial/"><div class="recent-posts-item-content">JavaScript 内存泄漏教程</div></a>
      </div>
    
  </div>
</div>
  </article>
  
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    关注嘉然！顿顿解馋！
  </div>
  <div class="recent-posts-list">
    
      <img 
        src="https://api2.mubu.com/v3/document_image/2697c6ae-10ee-41a3-9099-304bdb252d31-3807603.jpg" 
        class="myadd-img" 
        alt="author avatar">
    
  </div>
</div>
  </article>
</div>
            </aside>
          </div>
        </div>
      </div>
    </div>
     
    <footer class="footer">
  <div class="footer-container">
    <div>
      <div class="footer-dsc">
        <span>
          Copyright ©
          
            2020 -
          
          2022
        </span>
        &nbsp;
        <a 
          href="/" 
          class="footer-link">
          霜序廿的个人网站
        </a>
      </div>
    </div>

    
      <div class="footer-dsc">
        
          Powered by
          <a 
            href="https://hexo.io/" 
            class="footer-link" 
            target="_blank" 
            rel="nofollow noopener noreferrer">
            &nbsp;Hexo
          </a>
        
        
          <span>&nbsp;|&nbsp;</span>
        
        
          Theme -
          <a 
            href="https://github.com/theme-kaze" 
            class="footer-link" 
            target="_blank"
            rel="nofollow noopener noreferrer">
            &nbsp;Kaze
          </a>
        
      </div>
    
    
    
    
</footer> 
    
  <a 
    role="button" 
    id="scrollbutton" 
    class="basebutton" 
    aria-label="回到顶部">
    <i class="iconfont icon-arrowleft button-icon"></i>
  </a>

<a 
  role="button" 
  id="menubutton" 
  class="basebutton">
  <i class="iconfont icon-menu button-icon"></i>
</a>
<a 
  role="button" 
  id="popbutton" 
  class="basebutton" 
  aria-label="控制中心">
  <i class="iconfont icon-expand button-icon"></i>
</a>
<a 
  role="button" 
  id="darkbutton" 
  class="basebutton darkwidget" 
  aria-label="夜色模式">
  <i class="iconfont icon-weather button-icon"></i>
</a>
<a 
  role="button" 
  id="searchbutton" 
  class="basebutton searchwidget" 
  aria-label="搜索">
  <i class="iconfont icon-search button-icon"></i>
</a> 
     
     
     
      <script>
  var addImgLayout = function () {
    var img = document.querySelectorAll('.post-content img')
    var i
    for (i = 0; i < img.length; i++) {
      var wrapper = document.createElement('a')
      wrapper.setAttribute('href', img[i].getAttribute('data-src'))
      wrapper.setAttribute('aria-label', 'illustration')
      wrapper.style.cssText =
        'width: 100%; display: flex; justify-content: center;'
      if (img[i].alt) wrapper.dataset.caption = img[i].alt
      wrapper.dataset.nolink = true
      img[i].before(wrapper)
      wrapper.append(img[i])
      var divWrap = document.createElement('div')
      divWrap.classList.add('gallery')
      wrapper.before(divWrap)
      divWrap.append(wrapper)
    }
    baguetteBox.run('.gallery')
  }
</script>
<script>
  loadScript(
    "/js/lib/lightbox/baguetteBox.min.js",
    addImgLayout
  )
</script>
 
     
     
    <script src="/js/main.js"></script> 
     
    
      <script>
        var addLazyload = function () {
          var observer = lozad('.lozad', {
            load: function (el) {
              el.srcset = el.getAttribute('data-src')
            },
            loaded: function (el) {
              el.classList.add('loaded')
            },
          })
          observer.observe()
        }
      </script>
      <script>
        loadScript('/js/lib/lozad.min.js', addLazyload)
      </script>
     
    
    
  </body>
</html>
